package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 *  假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
 * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数。
 * <p>
 * 考虑
 * 在procecss的参数中 N和P是固定不变的
 * M和K是在不断变化的,并且在递归过程中是会出现M和K的重复对
 * 因此，我们可以把proceess()的结果和M,K的取值做一个对应关系，
 * 相当于做一个缓存
 */
public class 机器人行走问题解法3 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6};
        int result = function(5, 4, 2, 4);
        System.out.println(result);
    }

    private static int function(int N, int P, int M, int K) {
        if (P < 0 || P > N || M > N || M < 0 || K < 0) {
            return 0;
        }
        int[][] dp = new int[N + 1][K + 1];//注意 这里M+1和K+1的原因是 数组下标从0开始，我们要想
        //在这个二维数组中找到M和K的每一个对应关系，就必须+1
        dp[P][0]=1;
        for (int i = 1; i <=K; i++) {
            dp[1][i] = dp[2][i - 1];
            for (int j = 2; j <N; j++) {
                dp[i][j] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
            }
            dp[N][i] = dp[N - 1][i - 1];
        }
        return dp[M][K];
    }

    /**
     * @param P 最终需要到达的位置
     * @param M 机器人当前的位置
     * @param K 当前嗨能走的步数
     * @return
     */
    public static int process(int N, int P, int M, int K, int[][] cache) {
        if (cache[M][K] != -1) {
            System.out.println("走缓存");
            return cache[M][K];//表示缓存在，直接取缓存
        }
        if (K == 0) {//表示当前步数已经走完了
            //如果已经走到的目标位置，表名当前是一种方法，否则不是
            return P == M ? 1 : 0;
        }
        if (M == 1) {
            //如果机器人来到1位置，那么下一步只能往右来到2位置；
            return process(N, P, 2, K - 1, cache);
        }

        if (M == N) {
            // 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
            return process(N, P, N - 1, K - 1, cache);
        }
        return process(N, P, M - 1, K - 1, cache) + process(N, P, M + 1, K - 1, cache);

    }


}
